数据结构学习笔记＜3＞ 队列

一、队列的抽象数据类型描述

类型名：队列（Queue） 数据对象集：一个有 0 个或多个元素的有穷线性表 操作集：长度为 MaxSize 的堆栈 Q∈Queue, 队列元素 item∈ElementType

1.生成长度为 MaxSize 的空队列 Queue CreatQueue(int MaxSize); 2.判断队列 Q 是否已满 bool IsFullQ(Queue Q, int MaxSize); 3.将数据元素 item 插入队列 Q 中 bool AddQ(Queue Q, ElementType item); 4.判断队列 Q 是否已空 bool IsEmptyQ(Queue Q); 5.删除并返回队首元素 ElementType DeleteQ(Queue Q);

二、队列的顺序存储实现

1.定义

队列的顺序存储结构通常由一个一维数组和一个记录队列头元素位置的变量 front以及一个记录队列尾元素位置的变量 rear组成。 形成的数组搬过来，变成一个环，便为循环队列。 为了判断队列的空与满，循环队列仅使用 n-1 个数组空间 定义代码如下

typedef struct QNode *Queue;
struct QNode {
    ElementType Data[MaxSize];//一维数组
    int rear;//记录队列尾元素位置
    int front;//记录队列头元素位置
    int MaxSize;
    //实际上front指向的是队列头元素下标的前一个
};

2.操作

(1)创建循环队列(CreateQueue)

Queue CreateQueue( int MaxSize ) {
    Queue Q = (Queue)malloc(sizeof(struct QNode));
    Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
    Q->front = Q->rear = 0;
    Q->MaxSize = MaxSize;
    return Q;
}

(2)判断队列是否已满(IsFull)

bool IsFull( Queue PtrQ ) {//front和rear+1的取余相等时队列满
    return ((PtrQ->rear+1) % PtrQ->MaxSize == PtrQ->front);
}

(3)入队列(AddQ)

入队时要判断队列是否已满

bool AddQ(Queue PtrQ, ElementType item) {
    if ( IsFull(PtrQ) ) {
        printf("队列满");//front和rear+1的取余相等时队列满
        return false;
    } else {
     PtrQ->rear = (PtrQ->rear+1) % PtrQ->MaxSize;
     //移动队尾rear 以取余运算来实现循环
     PtrQ->Data[PtrQ->rear] = item;
     return true;
    }
}

(4)判断队列是否已空(IsEmpty)

bool IsEmpty(Queue PtrQ) {
    return ( PtrQ->front == PtrQ->rear );
}

(5)出队列(DeleteQ)

出队时判断当前队列是否为空

ElementType DeleteQ(Queue PtrQ) {
    if(IsEmpty(PtrQ)) {//rear和front相等时队列空
        printf("队列空");
        return false;
    } else {
        PtrQ->front = (PtrQ->front+1) % PtrQ->MaxSize;//移动队首front
        return PtrQ->Data[PtrQ->front];
    }
}

三、队列的链式存储实现

1.定义

队列的链式存储结构也可以用一个单链表实现，插入和删除操作分别在链表的两头进行。队列指针 front 应该指向链表头

struct Node {
    ElementType Data;
    struct Node * Next;
}
struct QNode {//链队列结构
    struct Node *rear;  //指向队尾结点
    struct Node *front;  //指向队头结点
};
typedef struct QNode *Queue;
Queue PtrQ;

2.操作

(1)不带头结点的链式队列初始化（ CreateQueue）

Queue CreateQueue() {
    Queue Q;
    Q = (Queue)malloc(sizeof(struct QNode));
    Q->front = Q->rear = NULL;//两个指针都为空
    return Q;
}

(2)不带头结点的链式队列入队操作

bool AddQ(Queue PtrQ, ElementType item) {
 struct Node *RearCell = PtrQ->rear;//指向队尾元素的指针
 struct Node *Temp = (struct Node *) malloc(sizeof(struct Node));
 Tmp->Data = X;
 Tmp->Next = NULL;
    if ( PtrQ->front == NULL ) {//队列为空 进第一个元素
        PtrQ->rear = PtrQ->front = Tmp;
    } else {
     RearCell->Next = Tmp;
     PtrQ->rear = Tmp;
    }
    return true;
}

(3)不带头结点的链式队列出队操作

ElementType DeleteQ(Queue PtrQ) {
    struct Node * FrontCell;
    ElementType FrontElem;//队首元素的值

    if (PtrQ->front == NULL) {//1.先判断是否为空 为空无法进行出队操作
        printf("队列空");
        return ERROR;
    }
    FrontCell = PtrQ->front;
    if(PtrQ->front == PtrQ->rear) //若队列只有一个元素 则删除后队列置为空
        PtrQ->front = PtrQ->rear = NULL;
    else
        PtrQ->front = FrontCell->Next;
    FrontElem = FrontCell->Data;
    free(FrontCell);    //释放被删除结点的空间
    return FrontElem;
}